#include <string_view>
#include <utility>
#include <vector>

using std::vector;

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode* left, TreeNode* right) : val(x), left(left), right(right) {}
};

class Solution {
public:
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        TreeNode* root = new TreeNode();
        build(root, preorder, 0, inorder, 0, preorder.size());
        return root;
    }

    static void build(TreeNode* node, vector<int>& preorder, int prestart, vector<int>& inorder, int instart, int len) {
        int k = 0;
        while (k < len && preorder[prestart] != inorder[instart + k]) {
            k++;
        }
        node->val = preorder[prestart];
        int l_len = k;
        int r_len = len - k - 1;
        if (l_len > 0) {
            node->left = new TreeNode();
            build(node->left, preorder, prestart + 1, inorder, instart, l_len);
        }
        if (r_len > 0) {
            node->right = new TreeNode();
            build(node->right, preorder, prestart + k + 1, inorder, instart + k + 1, r_len);
        }
    }
};